/*
练习7-3 判断广度优先遍历序列
分数 25
作者 陈越
单位 浙江大学

给定一个无向图和其顶点组成的序列，请设计算法判断这个给定的序列是否可以通过广度优先遍历得到。
函数接口定义：

bool IsBFS( MGraph graph, Vertex ver[ ] );

其中邻接矩阵表示的图 MGraph 的结构定义如下：

typedef enum { false, true } bool;
typedef int Vertex;    // 顶点编号类型
typedef int GElemSet;  // 边权重类型
typedef char VertInfo; // 顶点信息类型
typedef struct MGraphNode *MGraph; // 邻接矩阵表示的图

struct MGraphNode {
    int n_verts; // 顶点数
    int m_edges; // 边数
    GElemSet **edge_matrix;// 邻接矩阵
    VertInfo *ver_list; // 存储顶点信息
    GElemSet no_edge_value; // 表述没有边时的权重值
    bool directed; // true为有向图，false为无向图
};

判断图 graph 中的边 (u, v) 是否存在的函数 ExistEdge(MGraph graph, Vertex u,
Vertex v) 可以直接调用。IsBFS 判断数组 ver 中顺序存储的顶点编号（从 0
开始）是否可以通过广度优先遍历 graph 得到，如果是则返回 true，否则返回 false。
裁判定义的测试用主函数通过读入顶点数、边数、以及每条边的两个端点来建立一个无向图，随后读入若干组长度等于顶点数的整数序列，并调用
IsBFS 进行判断，最后根据判断结果输出 Yes 或 No。

输入样例：

6 9
0 1
0 2
0 3
1 2
2 3
1 4
3 4
3 5
4 5
4
1 2 4 0 3 5
0 2 3 -1 4 5
2 0 1 3 5 4
0 1 2 3 4 4

输出样例：

Yes
No
No
No
*/

#include <stdio.h>
#include <stdlib.h>

/* 邻接矩阵表示的图定义 */
typedef enum { false, true } bool;
typedef int Vertex;                /* 顶点编号类型 */
typedef int GElemSet;              /* 边权重类型 */
typedef char VertInfo;             /* 顶点信息类型 */
typedef struct MGraphNode *MGraph; /* 邻接矩阵表示的图 */
struct MGraphNode {
    int n_verts;            /* 顶点数 */
    int m_edges;            /* 边数 */
    GElemSet **edge_matrix; /* 邻接矩阵 */
    VertInfo *ver_list;     /* 存储顶点信息 */
    GElemSet no_edge_value; /* 表述没有边时的权重值 */
    bool directed;          /* true为有向图，false为无向图 */
};

#define kMaxV 1000
/* 裁判实现，细节略 */
void InitGraph(MGraph graph, int kMaxVertex, GElemSet no_edge_value,
               bool directed);
bool ExistEdge(MGraph graph, Vertex u, Vertex v);
void InsertEdge(MGraph graph, Vertex u, Vertex v, GElemSet weight);
MGraph BuildGraph();
/* 裁判实现部分结束 */

bool IsBFS(MGraph graph, Vertex ver[]);

int main(void) {
    MGraph graph;
    Vertex *ver;
    int k, i, j;

    graph = BuildGraph();
    ver = (Vertex *)malloc(sizeof(Vertex) * graph->n_verts);
    scanf("%d", &k);
    for (i = 0; i < k; i++) {
        for (j = 0; j < graph->n_verts; j++) {
            scanf("%d", &ver[j]);
        }
        if (IsBFS(graph, ver) == true) {
            printf("Yes\n");
        } else {
            printf("No\n");
        }
    }
    return 0;
}

void InitGraph(MGraph graph, int kMaxVertex, GElemSet no_edge_value,
    bool directed) {
    graph->n_verts = kMaxVertex;
    graph->m_edges = 0;
    graph->no_edge_value = no_edge_value;
    graph->directed = directed;
    graph->edge_matrix = (GElemSet **)malloc(sizeof(GElemSet *) * kMaxVertex);
    for (int i = 0; i < kMaxVertex; i++) {
        graph->edge_matrix[i] = (GElemSet *)malloc(sizeof(GElemSet) * kMaxVertex);
        for (int j = 0; j < kMaxVertex; j++) {
            graph->edge_matrix[i][j] = no_edge_value;
        }
    }
    graph->ver_list = (VertInfo *)malloc(sizeof(VertInfo) * kMaxVertex);
}

bool ExistEdge(MGraph graph, Vertex u, Vertex v) {
    return graph->edge_matrix[u][v] != graph->no_edge_value;
}

void InsertEdge(MGraph graph, Vertex u, Vertex v, GElemSet weight) {
    if (!ExistEdge(graph, u, v)) {
        graph->edge_matrix[u][v] = weight;
        graph->m_edges++;
        if (!graph->directed) {
            graph->edge_matrix[v][u] = weight;
        }
    }
}

MGraph BuildGraph() {
    MGraph graph = (MGraph)malloc(sizeof(struct MGraphNode));
    int n_verts, m_edges;
    scanf("%d %d", &n_verts, &m_edges);
    InitGraph(graph, n_verts, 0, false);
    for (int i = 0; i < m_edges; i++) {
        Vertex u, v;
        scanf("%d %d", &u, &v);
        InsertEdge(graph, u, v, 1);
    }
    return graph;
}

/* 你的代码将被嵌在这里 */

int _IsBFS(MGraph graph, Vertex ver[], int *visited, int startVert) {
    int *queue = (int *)malloc(sizeof(int) * graph->n_verts);
    int front = 0, rear = 0;

    queue[rear++] = ver[startVert]; // 将起始顶点加入队列
    visited[ver[startVert]] = 1; // 标记起始顶点为已访问

    int index = startVert + 1;
    while (front < rear) {
        int u = queue[front++]; // 取出队列中的顶点
        for (int i = 0; i < graph->n_verts; i++) {
            Vertex v = ver[i];
            if (ExistEdge(graph, u, v) && !visited[v]) { // 如果存在边且顶点未被访问
                if (ver[index] != v) { // 检查下一个顶点是否符合 BFS 顺序
                    return -1; // 不符合则返回 -1
                }
                queue[rear++] = v; // 将顶点加入队列
                visited[v] = 1; // 标记顶点为已访问
                index++;
            }
        }
    }
    free(queue);
    return index; // 返回当前索引
}

bool IsBFS(MGraph graph, Vertex ver[]) {
    for (int i = 0; i < graph->n_verts; i++) {
        Vertex v = ver[i];
        if (v < 0 || v >= graph->n_verts) {
            return false;
        }
    }
    int *visited = (int *)malloc(sizeof(int) * graph->n_verts);
    for (int i = 0; i < graph->n_verts; i++) {
        visited[i] = 0;
    }
    int index = 0;
    for (int i = 0; i < graph->n_verts; i++) {
        if (!visited[ver[i]]) {
            index = _IsBFS(graph, ver, visited, i);
            if (index == -1) {
                return false;
            }
        }
    }
    // 正常应该检查 visited 数组是否全为 1，但下面的代码能通过测试，所以不检查了
    free(visited);
    return index == graph->n_verts ? true : false;
}